#二叉树遍历

#树的遍历

#递归遍历

#前序遍历
def preorderTraversal(tree):
    result = []
    def preorder(tree):
        if tree:
            result.append(tree.val) #中
            preorder(tree.left) #左
            preorder(tree.right) #右
    preorder(tree)
    return result

#中序遍历
def inorderTraversal(tree):
    result = []
    def inorder(tree):
        if tree:
            inorder(tree.left)
            result.append(tree.val)
            inorder(tree.right)
    inorder(tree)
    return result

#后序遍历
def postorderTraversal(tree):
    result = []
    def postorder(tree):
        if tree:
            postorder(tree.left)
            postorder(tree.right)
            result.append(tree.val)
    postorder(tree)
    return result

#迭代遍历1

#前序遍历
def preorderTraversal(tree):
    if not tree:
        return []
    stack = [tree]
    result = []
    while stack:                        #stack:[node]-->[right, left]
        node = stack.pop()              #中
        result.append(node.val)
        if node.right:
            stack.append(node.right)    #右
        if node.left:
            stack.append(node.left)     #左
    return result

#中序遍历
def inorderTraversal(tree):
    if not tree:
        return []
    stack = []
    result = []
    cur = tree
    while cur or stack:
        if cur:                          #stack:[tree]-->[left]-->[left]
            stack.append(cur)
            cur = cur.left
        else:       
            cur = stack.pop()            #[left]-->[node]
            result.append(cur.val)
            cur = cur.right              #[node]-->[right]
    return result

#后序遍历
def postorderTraversal(tree):
    if not tree:
        return []
    stack = [tree]
    result = []
    while stack:                        #stack:[node]-->[left, right]
        node = stack.pop()              #中
        result.append(node.val)
        if node.left:
            stack.append(node.left)     #左
        if node.right:
            stack.append(node.right)    #右
    return result[::-1]                 #逆序

#迭代遍历2

#前序遍历
def preorderTraversal(tree):
    if not tree:
        return []
    result = []
    stack= [tree]
    while stack:
        node = stack.pop()
        if node :                           #右-左-(中,None)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            stack.append(node)
            stack.append(None)
        else:
            node = stack.pop()
            result.append(node.val)
    return result

#中序遍历
def inorderTraversal(tree):
    if not tree:
        return []
    result = []
    stack = [tree]
    while stack:
        node = stack.pop()
        if node :                           #右-(中,None)-左
            if node.right:
                stack.append(node.right)
            stack.append(node)
            stack.append(None) 
            if node.left:
                stack.append(node.left)
        else:
            node = stack.pop()
            result.append(node.val)
    return result

#后序遍历
def postorderTraversal(tree):
    if not tree:
        return []
    result = []
    stack = [tree]
    while stack:
        node = stack.pop()
        if node :                           #(中,None)-右-左
            stack.append(node)
            stack.append(None)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        else:
            node = stack.pop()
            result.append(node.val)
    return result



#层序遍历

#递归遍历
#层序遍历
def levelOrder(tree):
    res = []
    def level(tree, depth):
        if not tree: return []
        if len(res) == depth: res.append([])
        res[depth].append(tree.val)
        if  tree.left: level(tree.left, depth + 1)
        if  tree.right: level(tree.right, depth + 1)
    level(tree, 0)
    return res

#迭代遍历
#层序遍历
def levelOrder(tree):
    if not tree:
        return []
    results = []
    stack = [tree]
    while stack:
        size = len(stack)
        result = []
        for _ in range(size):
            cur = stack.pop(0)
            result.append(cur.val)
            if cur.left:
                stack.append(cur.left)
            if cur.right:
                stack.append(cur.right)
        results.append(result)
    return results